package leetcode.primary.array;

import java.util.Arrays;

/**
 * TODO 旋转数组：给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数
 * demo:输入: numbs = [1,2,3,4,5,6,7], k = 3
 * 输出: [5,6,7,1,2,3,4]
 *
 * @author david
 * @version 1.0
 * @date 2021/4/23 10:24
 */
public class Rotate {
    public static void main(String[] args) {
        int[] numbs = new int[]{1, 2, 3, 4, 5, 6, 7};
        int k = 4;
        System.out.println(Arrays.toString(rotate(numbs, k)));
    }

    /**
     * 使用临时数组解决
     * @param numbs
     * @param k
     * @return
     */
    static int[] rotate(int[] numbs, int k) {
        //取余得到位移步数
        int length = numbs.length;
        int[] temp = new int[length];
        //把原数组值放到一个临时数组中，
        //把原数组值放到一个临时数组中，
        System.arraycopy(numbs, 0, temp, 0, length);
        //然后在把临时数组的值重新放到原b数组，并且往右移动k位
        for (int i = 0; i < length; i++) {
            numbs[(i + k) % length] = temp[i];
        }
        return numbs;
    }


    /**
     * 多次反转 的方式解决
     * @param numbs
     * @param k
     */
    public static void rotate1(int[] numbs, int k) {
        int length = numbs.length;
        k %= length;
        reverse(numbs, 0, length - 1);//先反转全部的元素
        reverse(numbs, 0, k - 1);//在反转前k个元素
        reverse(numbs, k, length - 1);//接着反转剩余的
    }

    //把数组中从[start，end]之间的元素两两交换,也就是反转
    public static void reverse(int[] numbs, int start, int end) {
        while (start < end) {
            int temp = numbs[start];
            numbs[start++] = numbs[end];
            numbs[end--] = temp;
        }
    }
}
